import java.util.LinkedList;
import java.util.Queue;
//
//class Solution {
//    int[] dx={0,0,1,-1};
//    int[] dy={1,-1,0,0};
//
//    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
//        if(image[sr][sc]==color) return image;
//        int prev=image[sr][sc];
//        int m=image.length,
//                n=image[0].length;
//        image[sr][sc]=color;
//        Queue<int[]> q=new LinkedList();
//
//        q.add(new int[]{sr,sc});
//        while(!q.isEmpty()){
//            int[] arr=q.poll();
//
//            for(int i=0;i<4;i++){
//                int x=arr[0]+dx[i];
//                int y=arr[1]+dy[i];
//                if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev){
//                    image[x][y]=color;
//                    q.add(new int[]{x,y});
//                }
//            }
//        }
//        return image;
//    }
//}

class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int count = 0;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        int m = grid.length;
        int n = grid[0].length;
        boolean[][] vis = new boolean[m][n]; // 使用布尔数组代替整型数组，节省空间

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1' && !vis[i][j]) {
                    count++;
                    bfs(grid, vis, i, j, m, n);
                }
            }
        }

        return count;
    }

    private void bfs(char[][] grid, boolean[][] vis, int x, int y, int m, int n) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        vis[x][y] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];

            for (int k = 0; k < 4; k++) {
                int nx = cx + dx[k];
                int ny = cy + dy[k];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1' && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }
}